import javafx.util.Pair;

import java.util.*;

/**
* @description: 870. 优势洗牌
* @author hewei
* @date 2022/9/14 15:54
* @version 1.0
*/

public class AdvantageCount {

    public static void main(String[] args) {
        int[] nums1 = {2,0,4,1,2}, nums2 = {1,3,0,0,2};
        System.out.println(Arrays.toString(new AdvantageCount().advantageCount(nums1, nums2)));
    }

    public int[] advantageCount1(int[] nums1, int[] nums2) {
        PriorityQueue<Pair<Integer, Integer>> heap = new PriorityQueue<>((a, b) -> {
            Integer aKey = a.getKey();
            Integer bKey = b.getKey();
            Integer valueA = aKey == 1 ? nums1[a.getValue()] : nums2[a.getValue()];
            Integer valueB = bKey == 1 ? nums1[b.getValue()] : nums2[b.getValue()];
            if (aKey.equals(bKey)) {
                return valueA - valueB;
            } else {
                if (!valueA.equals(valueB)) return valueA - valueB;
                return aKey == 1 ? -1 : 1;
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            heap.add(new Pair<>(1, i));
            heap.add(new Pair<>(2, i));
        }
        Deque<Integer> queue = new LinkedList<>();
        int lastType = 1;
        Deque<Integer> index = new LinkedList<>();
        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);
        while (!heap.isEmpty()) {
            Pair<Integer, Integer> poll = heap.poll();
            if (poll.getKey() == 1) {
                if (lastType == 1 && index.isEmpty()) {
                    queue.add(nums1[poll.getValue()]);
                } else if (!index.isEmpty()) {
                    ans[index.poll()] = nums1[poll.getValue()];
                }
                if (lastType != 1) lastType = 1;
            } else {
                lastType = 2;
                index.add(poll.getValue());
            }
        }
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == -1) ans[i] = queue.poll();
        }
        return ans;
    }

    public int[] advantageCount(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> heap1 = new PriorityQueue<>();
        PriorityQueue<Integer> heap2 = new PriorityQueue<>(Comparator.comparingInt(a -> nums2[a]));
        for (int i = 0; i < nums1.length; i++) {
            heap1.add(nums1[i]);
            heap2.add(i);
        }
        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);
        Deque<Integer> queue = new LinkedList<>();
        while (!heap1.isEmpty()) {
            Integer poll = heap1.poll();
            if (poll <= nums2[heap2.peek()]) {
                queue.add(poll);
            } else {
                Integer temp = heap2.poll();
                ans[temp] = poll;
            }
        }
        while (!heap2.isEmpty()) {
            ans[heap2.poll()] = queue.poll();
        }
        return ans;
    }
}